/*
 * @lc app=leetcode id=130 lang=cpp
 *
 * [130] Surrounded Regions
 */
class Solution {
private:
    const vector<vector<int>> opset = { {-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
    void solve(vector<vector<char>>& board) {
        int row = board.size();
        if (row < 3) {
            return ;
        }
        int col = board[0].size();
        if (col < 3) {
            return ;
        }

        vector<vector<bool>> visited(row, vector<bool>(col, false));

        for (int i = 1; i < row-1; i++) {
            for (int j = 1; j < col-1; j++) {
                if (board[i][j] == 'O' && !visited[i][j]) {
                    bool flag = true;
                    vector<vector<int>> path;
                    dfs(board, i, j, flag, path, visited);
                    if(flag) {
                        for (auto pos : path) {
                            board[pos[0]][pos[1]] = 'X';
                        }
                    }
                }
            }
        }
    }

    void dfs(vector<vector<char>>& board, int i, int j, bool& flag,
            vector<vector<int>>& path, vector<vector<bool>>& visited) {
        int row = board.size();
        int col = board[0].size();

        visited[i][j] = true;
        if (i == row-1 || j == col-1 || i == 0 || j == 0) {
            flag = false;
            return ;
        }
        path.push_back({i, j});

        int x, y;
        for (auto op : opset) {
            x = i + op[0];
            y = j + op[1];
            if (posValid(x, y, row, col) && !visited[x][y] && board[x][y] == 'O') {
                dfs(board, x, y, flag, path, visited);
            }
        }
        return ;
    }

    bool posValid(int x, int y, int row, int col) {
        return x >= 0 && x < row && y >= 0 && y < col;
    }
};

